home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / incl / LEDA / ugraph2.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  5.8 KB  |  208 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  ugraph2.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #ifndef LEDA_UGRAPH_H
  17. #define LEDA_UGRAPH_H
  18.  
  19. #include <LEDA/graph.h>
  20.  
  21.  
  22. //-----------------------------------------------------------------------------
  23. // ugraph: base class for all undirected graphs
  24. //-----------------------------------------------------------------------------
  25.  
  26. class ugraph : public graph{
  27.  
  28. private:
  29.  
  30. edge sym_edge(edge e) const { return e->rev; }
  31.  
  32.  
  33. public:
  34.  
  35.  
  36. edge new_edge(node v,node w,GenPtr i);
  37. edge new_edge(node v,node w,edge e1,edge e2,GenPtr i,int d1,int d2) ;
  38.  
  39. edge new_edge(node v,node w)
  40. { GenPtr x; init_edge_entry(x);
  41.   return new_edge(v,w,x);
  42.  }
  43.  
  44. edge new_edge(node v, node w, edge e1 ,edge e2, int dir1=0,int dir2=0)
  45. { GenPtr x; init_edge_entry(x);
  46.   return new_edge(v,w,e1,e2,x,dir1,dir2);
  47.  }
  48.  
  49. void del_edge(edge);
  50.  
  51. void rev_edge(edge) {}
  52.  
  53. node opposite(node v, edge e)  const { return (v==e->s) ? e->t : e->s; }
  54.  
  55. list<node> adj_nodes(node) const;
  56.  
  57. edge adj_succ(edge e,node v)  const
  58. { if (v==e->t) e = sym_edge(e);
  59.   return graph::adj_succ(e);
  60.  }
  61.  
  62. edge adj_pred(edge e,node v)  const
  63. { if (v==e->t) e = sym_edge(e);
  64.   return graph::adj_pred(e);
  65.  }
  66.  
  67. edge cyclic_adj_succ(edge e,node v)  const
  68. { if (v==e->t) e = sym_edge(e);
  69.   return graph::cyclic_adj_succ(e);
  70.  }
  71.  
  72. edge cyclic_adj_pred(edge e,node v)  const
  73. { if (v==e->t) e = sym_edge(e);
  74.   return graph::cyclic_adj_pred(e);
  75.  }
  76.  
  77.  
  78. void print_edge(edge, ostream& = cout) const;
  79.  
  80. void read(string s)    { graph::read(s);  make_undirected(); } 
  81. void read(istream& in) { graph::read(in); make_undirected(); } 
  82.  
  83. ugraph()  { undirected = true; }
  84.  
  85. ugraph(const graph& a): graph(a) { undirected = true;  make_undirected(); }
  86.  
  87. ugraph(const ugraph& a) : graph(a)  { undirected = true;  }
  88.  
  89. ~ugraph() { /* ~graph does the job */ }
  90.  
  91. //subgraph constructors
  92. ugraph(ugraph&, const list<node>&, const list<edge>&);
  93. ugraph(ugraph&, const list<edge>&);
  94.  
  95. ugraph& operator=(const ugraph& a) { graph::operator=(a); return *this; }
  96.  
  97. ugraph& operator=(const graph& a)  { graph::operator=(a); 
  98.                                      make_undirected(); 
  99.                                      return *this;
  100.                                     }
  101.  
  102. };
  103.  
  104.  
  105.  
  106. //------------------------------------------------------------------------------
  107. // UGRAPH: generic ugraphs
  108. //------------------------------------------------------------------------------
  109.  
  110.  
  111. template<class vtype, class etype>
  112.  
  113. class _CLASSTYPE UGRAPH : public ugraph {
  114.  
  115. vtype X;
  116. etype Y;
  117.  
  118. void copy_node_entry(GenPtr& x) const { x=Copy(ACCESS(vtype,x)); }
  119. void copy_edge_entry(GenPtr& x) const { x=Copy(ACCESS(etype,x)); }
  120.  
  121. void clear_node_entry(GenPtr& x) const { Clear(ACCESS(vtype,x)); }
  122. void clear_edge_entry(GenPtr& x) const { Clear(ACCESS(etype,x)); }
  123.  
  124. void write_node_entry(ostream& o, GenPtr& x) const{ Print(ACCESS(vtype,x),o);}
  125. void write_edge_entry(ostream& o, GenPtr& x) const{ Print(ACCESS(etype,x),o);}
  126.  
  127. void read_node_entry(istream& i, GenPtr& x) { Read(X,i); x=Copy(X); }
  128. void read_edge_entry(istream& i, GenPtr& x) { Read(Y,i); x=Copy(Y); }
  129.  
  130. void init_node_entry(GenPtr& x) { Init(X); x = Copy(X); }
  131. void init_edge_entry(GenPtr& x) { Init(Y); x = Copy(Y); }
  132.  
  133. void print_node_entry(ostream& o, GenPtr& x)  const
  134.      { o << "("; Print(ACCESS(vtype,x),o); o << ")"; }
  135. void print_edge_entry(ostream& o, GenPtr& x)  const
  136.      { o << "("; Print(ACCESS(etype,x),o); o << ")"; }
  137.  
  138. char* node_type()  const { return TYPE_NAME(vtype); }
  139. char* edge_type()  const { return TYPE_NAME(etype); }
  140.  
  141. public:
  142.  
  143. int cmp_node_entry(node x, node y) const { return compare(inf(x),inf(y)); }
  144. int cmp_edge_entry(edge x, edge y) const { return compare(inf(x),inf(y)); }
  145.  
  146. vtype  inf(node v)         const { return ACCESS(vtype,ugraph::inf(v)); }
  147. etype  inf(edge e)         const { return ACCESS(etype,ugraph::inf(e)); }
  148. vtype& operator[] (node v)       { return ACCESS(vtype,entry(v)); }
  149. vtype  operator[] (node v) const { return ACCESS(vtype,ugraph::inf(v)); }
  150. etype& operator[] (edge e)       { return ACCESS(etype,entry(e)); }
  151. etype  operator[] (edge e) const { return ACCESS(etype,ugraph::inf(e)); }
  152. void   assign(node v,vtype x)    { graph::assign(v,Convert(x)); }
  153. void   assign(edge e,etype x)    { graph::assign(e,Convert(x)); }
  154.  
  155. node   new_node()        { return ugraph::new_node(); }
  156. node   new_node(vtype a) { return graph::new_node(Copy(a)); }
  157.  
  158. edge   new_edge(node v, node w) 
  159.                    { return ugraph::new_edge(v,w); }
  160.  
  161. edge   new_edge(node v, node w, etype a) 
  162.                    { return ugraph::new_edge(v,w,Copy(a)); }
  163. edge   new_edge(node v,node w,edge e1,edge e2,etype a,int dir1=0,int dir2=0)
  164.                    { return ugraph::new_edge(v,w,e1,e2,Copy(a),dir1,dir2); }
  165.  
  166. void   clear()     { clear_all_entries(); ugraph::clear(); }
  167.  
  168. UGRAPH<vtype,etype>& operator=(const UGRAPH<vtype,etype>& a)
  169. { clear_all_entries();
  170.   ugraph::operator=(*(ugraph*)&a);
  171.   copy_all_entries();
  172.   return *this;}
  173.  
  174. UGRAPH<vtype,etype>& operator=(const graph& a)
  175. { clear_all_entries();
  176.   ugraph::operator=(a);
  177.   copy_all_entries();
  178.   return *this;
  179.  }
  180.  
  181. UGRAPH() {}
  182.  
  183. UGRAPH(const UGRAPH<vtype,etype>& a): ugraph(*(ugraph*)&a) 
  184. { copy_all_entries(); }
  185.  
  186. UGRAPH(const graph& a) : ugraph(a)            
  187. { copy_all_entries(); }
  188.  
  189. ~UGRAPH() 
  190. { if (parent==0) clear_all_entries(); }
  191.  
  192. };
  193.  
  194.  
  195.  
  196. extern void complete_ugraph(ugraph&,int);
  197. extern void random_ugraph(ugraph&,int,int);
  198. extern void test_ugraph(ugraph&);
  199.  
  200. #ifndef __ZTC__
  201. inline void complete_graph(ugraph& U,int n)     { complete_ugraph(U,n); }
  202. inline void random_graph(ugraph& U,int n,int m) { random_ugraph(U,n,m); }
  203. inline void test_graph(ugraph& U)               { test_ugraph(U); }
  204. #endif
  205.  
  206.  
  207. #endif
  208.